#include "DynamicArray2.h"
#include <iostream>
#include <cmath>


DynamicArray::DynamicArray(size_t capacity):size(0),capacity(capacity)
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray& a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for(size_t i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
}

DynamicArray& DynamicArray::operator=(const DynamicArray& a)
{
    delete []array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for(size_t i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
    return *this;
}

DynamicArray::~DynamicArray()
{
    delete []array;
}

size_t DynamicArray::Size()
{
    return size;
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = (size > capacity) ? capacity : size;
    ElementType *newP = new ElementType[capacity];
    for(size_t i = 0; i < size; i++)
    {
        newP[i] = array[i];
    }
    delete []array;
    array = newP;
}

void DynamicArray::InsertTail(const ElementType& element)
{
    if(size >= capacity)
    {
        ReSize(2 * capacity);
    }
    array[size++] = element;
}

void DynamicArray::InsertHead(const ElementType& element)
{
    if(size >= capacity)
    {
        ReSize(2 * capacity);
    }
    for(int i = size; i > 0; i--)
    {
        array[i] = array[i-1];
    }
    array[0] = element;
    size++;
}

void DynamicArray::InsertByIndex(int index,const ElementType& element)
{
    if(index < 0 || index > size)
    {
        return;
    }
    if(size >= capacity)
    {
        ReSize(2 * capacity);
    }
    for(size_t i = size; i > index; i--)
    {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

void DynamicArray::RemoveByIndex(int index)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    for(int i = index; i < size - 1; i++)
    {
        array[i] = array[i + 1];
    }
    size--;
}

void DynamicArray::RemoveByElement(const ElementType& element)
{
    for(int i = 0; i < size; i++)
    {
        if(array[i] == element)
        {
            RemoveByIndex(i);
            i--; //删除两个相同且相邻的数
        }
    }
}

ElementType* DynamicArray::FindByIndex(int index) 
{
    if(index < 0 || index >= size)
    {
        return nullptr;
    }
    return &array[index];
}

DynamicArray DynamicArray::FindByElement(const ElementType& element)
{
    DynamicArray result;
    for(int i = 0; i < size; i++)
    {
        if(array[i] == element)
        {
            result.InsertTail(i);
        }
    }
    return result;
}

void DynamicArray::UpdateByIndex(int index,const ElementType& element)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    array[index] = element;
}

void DynamicArray::UpdateByElement(const ElementType& oldValue,const ElementType& newValue)
{
    for(int i = 0; i < size; i++)
    {
        if(oldValue == array[i])
        {
            array[i] = newValue;
        }
    }
}

void DynamicArray::show()
{
    for(int i = 0; i < size; i++)
    {
        std::cout<<array[i]<<" ";
    }
    std::cout<<std::endl;
}

void DynamicArray::InsertSort(size_t start,size_t end)
{
   for(size_t i = start; i <= end; i++)
   {
        size_t j = i;
        ElementType temp = array[i];
        for(;j > start; j--)
        {
            if(array[j - 1] > temp)
            {
                array[j] = array[j-1];
            }
            else
            {
                break;
            }
        }
        array[j] = temp;
   }
}

void DynamicArray::Sort()
{
    FastSort(0,size - 1,0,2 * log2(size));
}

size_t DynamicArray::Partition(size_t start,size_t end)
{
    size_t left = start;
    size_t right = end;
    ElementType temp = array[left];
    while(left < right)
    {
        while(left < right && array[right] > temp)
        {
            right--;
        }
        if(left < right)
        {
            array[left++] = array[right];
        }
        while(left < right && array[left] < temp)
        {
            left++;
        }
        if(left < right)
        {
            array[right--] = array[left];
        }
    }
    array[left] = temp;
    return left;
}

void DynamicArray::FastSort(size_t start,size_t end,size_t deep,size_t Maxdeep)
{
    if(start >= end)
    {
        return;
    }
    if(deep > Maxdeep)
    {
        InsertSort(start,end);
    }
    else
    {
        size_t per = Partition(start,end);
            if(per != 0)
        FastSort(start,per - 1,deep+1,Maxdeep);
        FastSort(per + 1,end,deep+1,Maxdeep);
    }
}

void DynamicArray::Duplicate()
{
    for(int i = 1; i < size; i++)
    {
        if(array[i] == array[i - 1])
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

DynamicArray DynamicArray::FdInterSctn(const DynamicArray &a)
{
    size_t first = 0;
    size_t second = 0;
    DynamicArray result;
    while(first < size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if (array[first] < a.array[second])
        {
            first++;
        }
        else
        {
            second++;
        }
    }
    return result;
}

DynamicArray DynamicArray::FdUnionSet(const DynamicArray &a)
{
    size_t first = 0;
    size_t second = 0;
    DynamicArray result;
    while(first < size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if (array[first] > a.array[second])
        {
            result.InsertTail(a.array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while(first < this->size)
        {
            result.InsertTail(array[first++]);
        }
    while(second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }
    return result;
}

DynamicArray DynamicArray::FdDiffernce(const DynamicArray &a)
{
    size_t first = 0;
    size_t second = 0;
    DynamicArray result;
    while(first < size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            first++;
            second++;
        }
        else if (array[first] > a.array[second])
        {
            result.InsertTail(a.array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while(first < this->size)
        {
            result.InsertTail(array[first++]);
        }
    while(second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }
    return result;
}

DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;
    size_t second = 0;
    while(first < this->size && second < a.size)
    {
        if(this->array[first] <= a.array[second])
        {
            result.InsertTail(array[first++]);
        }
        else
        {
            result.InsertTail(a.array[second++]);
        }
    }
        while(first < this->size)
        {
            result.InsertTail(array[first++]);
        }
        while(second < a.size)
        {
            result.InsertTail(a.array[second++]);
        }
    return result;
}

bool DynamicArray::operator==(const DynamicArray& a)
{
    if(size != a.size)
    {
        return false;
    }
    size_t first = 0;
    size_t second = 0;
    while(first < this->size && second < a.size)
    {
        if(array[first++] == array[second++])
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    return true;
}

size_t DynamicArray::BinarySearch(const ElementType& element)
{
    size_t left = 0;
    size_t right = size - 1;
    while(left <= right)
    {
        size_t mid = (left&right) + ((left^right)>>1);
        if(array[mid] == element)
        {
            return mid;
        }
        else if(array[mid] > element)
        {
            if(mid == 0)
            {
                return ULONG_MAX;
            }
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return ULONG_MAX;
}

bool DynamicArray::IsChild(const DynamicArray& a)
{
    // for(int i = 0; i < a.size; i++) 小循环
    // {
    //     if(FindByElement(a.array[i]).size == 0)
    //     {
    //         return false;
    //     }
    // }
    // return true;

    int j = 0;
    for(int i = 0; i < size; i++) //大循环
    {
        if(array[i] == a.array[j])
        {
            j++;
        }
    }
    return j == a.size;
}

DynamicArray DynamicArray::subsequence(int index,size_t size)
{
    if(index < 0 || index + size > this->size)
    {
        return DynamicArray();
    }
    DynamicArray result;
    for(int i = index; i < size; i++)
    {
        result.InsertTail(array[i]);
    }
    return result;
}

bool DynamicArray::IsContinueChild(const DynamicArray &a)
{
    for(int i = 0; i < size - a.size; i++)
    {
        if(subsequence(i,a.size) == a)
        {
            return true;
        }
    }
    return false;
}
